Next hop selection is a fundamental part of routing. In one example of a switch setting, multiple links may be built to the same destination for the purposes of redundancy, and then packets are hashed across one of the multiple links, so that if one of the links are lost, other links remain to carry traffic to the destination. A typical edge router may support Equal-Cost Multi-Path (ECMP) routing (defined as an IEEE standard in IEEE 802.1Qbp (part of IEEE—802.1); IETF RFC 2991 discusses multipath routing in general), which is implemented as follows: a hash function is applied to an incoming packet (e.g. based on the 5-tuple of <IP source, IP destination, IP protocol, source port, destination port>) and a modulo N operation is applied to the resulting hash value, where N is the number of equal cost paths available. When the set of paths changes (e.g. because a route is withdrawn), the majority of subsequent packets will hash to a different path, e.g., if the next hop for an address may terminate at different servers on a network, if the number of servers changes then the hash calculation will usually result in a different destination server and application connections will be broken.
For example, if there are two links to choose from link 0 and link 1, and the hash calculation on an address associated with a packet outputs a result ending in 10, the calculation 10 modulo 2 results in 0, and link 0 will be chosen. However, if a new link is added, e.g. link 2, such that there are now three links, if an address associated with the same packet is hashed to the same output ending in 10, the calculation 10 modulo 3 results in 1, and link 1 would be chosen, ultimately resulting in a different path through a different server. For stateful protocols such as TCP, and stateful applications such as SIP, this change results in disruptions to ongoing sessions and the desired efficiency from using ECMP routing is lost.
This type of routing disruption caused by servers joining or leaving the network is particularly problematic in the case of network virtualization. A virtual network consists, at least in part, of virtual network links that do not represent a physical (wired or wireless) connection between two computing devices but is mapped on top of physical infrastructure and implemented using methods of network virtualization. There is typically a more rapid change in the set of paths that exist in a virtual network compared to a physical network, because servers and end points become available and unavailable much more often in a virtual network. One reason for this rapid change is that it is much easier to set up a virtual machine compared to installing a new physical server.
Existing methods use algorithms that only partially ameliorate the problem of disruptions to ongoing sessions, for example, consistent hashing conceptually maps a packet to a virtual bin, and assigns bins to servers in such a way that removing a server affects at most 1/N mappings. However, existing implementations are not suitable for being embedded in a router. Likewise, ‘robust hashing’ is an algorithm which computes a hash value over the incoming packet and each path in the set; the results are sorted and the path with the highest hash value is selected. This has the same result of affecting at most 1/N mappings upon path changes, however calculating N hashes for each packet is resource-expensive and likewise not easily implemented in routers.
Additionally, prior art hashing algorithms built into OpenVSwitch; for example the ‘enum nx_mp_algorithm’ (https://github.com/osrg/openvswitch/blob/master/include/openflow/nicira-ext.h), enumerate a number of available options. Although some of the options are listed as ‘O(1)’, the CPU cycles required for these algorithms are still fairly expensive.
In view of the foregoing, it would be desirable to perform ECMP routing with minimal disruption to existing paths when the path set changes, such that the routing is efficient enough to be embedded in an existing router.